/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class LongestUnivaluePath {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	int max = 0;

	public int longestUnivaluePath(TreeNode root) {
		if (root == null) {
			return 0;
		}
		helper(root);
		return max - 1;
	}

	private int helper(TreeNode root) {
		int len = 1;
		int l = 0, r = 0;
		int up = 0;
		if (root.left != null) {
			l = helper(root.left);
			if (root.val == root.left.val) {
				len += l;
				up = l;
			}
		}
		if (root.right != null) {
			r = helper(root.right);
			if (root.val == root.right.val) {
				len += r;
				up = Math.max(up, r);
			}
		}
		max = Math.max(max, len);
		return up + 1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
